package xyz.scootaloo.oj.leetcode

import cn.hutool.core.lang.Console
import org.junit.Test
import kotlin.random.Random

/**
 * 未完成
 *
 * @author flutterdash@qq.com
 * @since 2021/5/1 10:37
 */
class P380 {

    class RandomizedSet() {
        /** Initialize your data structure here. */
        val map = HashMap<Int, Int>()
        val array = ArrayList<Int>()

        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        fun insert(`val`: Int): Boolean {
            return if (map.containsKey(`val`)) {
                false
            } else {
                map[`val`] = array.size
                array.add(`val`)
                return true
            }
        }

        /** Removes a value from the set. Returns true if the set contained the specified element. */
        fun remove(`val`: Int): Boolean {
            if (!map.containsKey(`val`))
                return false

            val lastElement = array[array.size - 1]
            val index = map[`val`]!!
            array[index] = lastElement
            map[lastElement] = index


            array.remove(array.size - 1)
            map.remove(`val`)
            return true
        }

        /** Get a random element from the set. */
        fun getRandom(): Int {
            if (array.size == 1)
                return array[0]
            val index = Random.nextInt(0, array.size)
            return array[index]
        }
    }

    @Test
    fun testRandom() {
        val random = RandomizedSet()
        Console.log(random.insert(1))
        Console.log(random.remove(2))
        Console.log(random.insert(2))
        Console.log(random.getRandom())
        Console.log(random.remove(1))
        Console.log(random.insert(2))
        Console.log(random.getRandom())
    }

}
